﻿#include <iostream>
#include <queue>

#define MIN(a, b) (a < b ? a : b)
using namespace std;

struct intComparator {
    bool operator()(int& a, int& b)
    {
        return a > b;
    }
};

static bool intCompare(int& a, int& b)
{
    return a > b;
}

static void sortedArrDistanceLessThanK(int* numbers, const size_t size, const int k) {
    priority_queue<int, vector<int>, decltype(&intCompare)> heap(intCompare);
    int index = 0;
    for (; index < MIN(size, k); index++) {
        heap.push(numbers[index]);
    }

    int i = 0;
    for (; index < size; i++, index++) {
        heap.push(numbers[index]);
        numbers[i] = heap.top();
        heap.pop();
    }

    while (!heap.empty()) {
        numbers[i++] = heap.top();
        heap.pop();
    }
}

// 交换数组中指定的两个索引的数字
static void swap(int* arr, const int i, const int j) {
    if (i == j) return;

    // a = a ^ b
    // b = a ^ b // a ^ b ^ b = a
    // a = a ^ b // a ^ b ^ a = b

    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

// 小根堆插入
static void heapInsert(int* arr, int index) {
    while (arr[index] < arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

// 小根堆index的元素下移
static void heapify(int* arr, int index, const size_t heapSize) {
    int left = index * 2 + 1;
    while (left < heapSize) {
        int right = left + 1;
        int smallest = right < heapSize && arr[right] < arr[left] ? right : left;
        smallest = arr[index] < arr[smallest] ? index : smallest;
        if (smallest == index) break;

        swap(arr, index, smallest);
        index = smallest;
        left = index * 2 + 1;
    }
}

static void sortedArrDistanceLessThanKBySelfHeap(int* arr, const size_t arrSize, int k) {
    k = MIN(arrSize, k);

    int* heapArr = (int*)malloc(k*sizeof(int));
    memcpy_s(heapArr, k*sizeof(int), arr, k*sizeof(int));

    for (int i = 1; i < k; i++) {
        heapInsert(heapArr, i);
    }
    
    int heapSize = k;

    int arrIndex = 0;
    for (int i = k; i < arrSize; i++, arrIndex++) {
        arr[arrIndex] = heapArr[0];
        heapArr[0] = arr[i];
        heapify(heapArr, 0, heapSize);
    }

    while (heapSize > 0) {
        arr[arrIndex++] = heapArr[0];
        swap(heapArr, 0, heapSize - 1);
        heapify(heapArr, 0, --heapSize);
    }

    free(heapArr);
}

// 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，
// 并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数组进行排序。
int main_SortArrayDistanceLessThanK()
{
    int arr[] = {3,4,8,1,2,12,10,9,7};
    size_t arrSize = sizeof(arr)/sizeof(int);

    int* arr2 = (int*)malloc(arrSize*sizeof(int));
    memcpy_s(arr2, arrSize*sizeof(int), arr, arrSize*sizeof(int));
    
    sortedArrDistanceLessThanK(arr, arrSize, 6);

    for (int i = 0; i < arrSize; i++) {
        printf("arr[%d]=%d\n", i, arr[i]);
    }

    printf("==============\n");

    sortedArrDistanceLessThanKBySelfHeap(arr2, arrSize, 6);

    for (int i = 0; i < arrSize; i++) {
        printf("arr2[%d]=%d\n", i, arr2[i]);
    }

    free(arr2);
    return 0;
}